Time division multiplexing (TDM) is a mechanism commonly used for sharing resources on a communication link. Consider for example a single “wire” connecting multiple voice or data channels between call switches of a telephone network. The link is divided in time into successive frames of equal duration. Each frame is further subdivided in time into a sequence of slots (e.g. numbered 0 to 31), where each slot can accommodate 8 bits. The number of slots in a frame is determined by the data rate of the link and the duration of the frame. Multiple channels are formed on a data stream by allocating respective slot numbers to channels. Thus, a first channel (CH0) is formed from the set of first slots in successive frames, a second channel (CH1) is formed from the set of second slots in successive frames, etc. A typical system may comprise 32 wires providing a total of 1024 data channels. A further two wires provide slot and frame synchronisation signals respectively.
Telephone network operators are keen to make use of packet networks to carry user traffic. For example, such packet networks may make use of the well known Internet Protocol (IP) to route data packets. In order to enable packet networks to interwork with conventional TDM networks, it will be necessary to provide a mechanism for efficiently converting between the TDM format and the packet format. FIG. 1 illustrates in very general terms a mechanism for facilitating the transparent flow of data between two TDM networks via a packet network. This mechanism must meet the following requirements:                Transmit constant bit rate TDM data across a packet network so that it can be reconstructed as TDM data at the far end;        Support the mapping of multiple TDM channels into a stream of packets (called a context) for transmission over a network;        Support multiple packet streams (contexts);        Maintain timeslot order when mapping TDM channels to and from context packets;        Each packet must contain one or more complete TDM frames of data; and        Packet transmission and reception must be aligned with the first TDM channel for the context after the TDM frame pulse.        
FIG. 2 illustrates in more detail the TDM-packet conversion units of FIG. 1. Within a unit, a TDM receive block assembles incoming TDM data into packets. The receiver can handle several packet streams at a time, where each packet stream represents a virtual channel connection or “context” over the packet network. Each packet comprises a header containing a context identifier. Different contexts may terminate at the same or different TDM-packet conversions units (for example associated with different network operators). Due to the large number of channels and high data rate which the system must handle, the conversion units are typically implemented in hardware.
A given context may carry several TDM channels. Packets are assembled sequentially. Data is placed into a packet as the data arrives at the (input) TDM port, maintaining channel and stream order (i.e. channel 0, stream 0 comes before channel 0, stream 1, which in turn comes before channel 1, stream 0). Each packet of a context must contain channel data belonging to one or more complete TDM frames—partial frames are not permitted—and each packet must start with the beginning of a new frame.
A TDM receive block makes use of a lookup table to map stream and channel number from the TDM interface to a context number. The lookup table additionally comprises a “channel flag” indicating whether or not individual channels on a given stream are in use. By way of example, a lookup table for a small TDM environment with four streams, each with four channels, is shown in FIG. 3. Data is written to the lookup table by the host control processor, with the hardware providing the receive block cycling through the entries in the table.
A TDM-packet conversion unit may terminate contexts from several different peer TDM-packet conversion units. Packets belonging to these contexts and received over the packet network are stored in a buffer (one for each context, although the buffers may be formed logically in the same memory device) of the receiving TDM-packet conversion unit. The TDM transmit block extracts data from the front of the buffers and transmits this on the appropriate TDM channels/streams. Again, a lookup table is used by the TDM transmit block to map context data to channels/streams (NB. the mapping may be, and most probably is, different from that used at the sending entity, although the structure of the table remains the same).
With reference again to FIG. 3 and assuming now that that table shows the mapping of contexts to channels/slots for the TDM output, it will be apparent that for context 1, the TDM transmit block will know that channel 0 of stream 0 is aligned with the start of a TDM frame. As the transmit block cycles through the lookup table, it will encounter a first entry for context 1 subsequent to that context becoming valid (i.e. the channel flag being set to Y). If that first encountered entry is that for channel 0/stream 0, the transmit block will know that a byte can be extracted from the context 1 buffer and sent on channel 0/stream 0. However, if the first encountered entry is any other entry, the transmit block will know that it must ignore the entry and continue cycling through the table until the channel 0/stream 0 entry is reached.
For contexts other than context 1 however, the transmit block has no knowledge of which entry is the first entry for a context. For example, assume that context 4 becomes valid (following the updating of the lookup table by the host control processor), and that at this time the transmit block has reached the channel number 3/stream number 2 entry of the lookup table. This is associated with context 4, and the channel flag will be set. The transmit block will extract the next byte from the context 4 buffer and send this on channel number 3/stream number 2. However, this byte should have been sent on channel number 3/stream number 0. The data therefore becomes misaligned with the start of the TDM frames. This is likely to have serious consequences as a given context may carry data associated with different calls. When misalignment occurs, a party to a call may receive data intended for some other party and vice versa. This problem of data misalignment within and between TDM frames following the updating of a lookup table by the host control processor arises also at the TDM receive block.